package dz_1;

import java.lang.reflect.Array;
import java.util.Random;

public class DZ_1 {
    
    //Сортировка подсчетом. Данная сортировка выгодна, когда диапазон значений достаточно мал.
    //Проверим время работы сортировки при разных диапозонах значений
    
    static void mySort(int[] arr) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)  
                max = arr[i];
            if (arr[i] < min) 
                min = arr[i];

        }
        int shift = max - min;
        int[] res = new int[shift + 1];
        for (int i = 0; i < arr.length; i++) {
            res[arr[i] - min] = res[arr[i] - min] + 1;
        }
        int count = 0;
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[i]; j++) {
                arr[count] = i + min;
                count++;
            }
        }
    }
    public static void main(String[] args) {
        Random rand = new Random();
        int length = 10000000;
        System.out.println("Количество элементов в массиве"+length);
        int[] arr = new int [length];
        
        
        System.out.println("Время сортировки при диапазоне значений 100:");
        for(int i = 0; i<length; i++){
            arr[i] = rand.nextInt(100);
        } 
        long t1,t2;
        t1 =  System.currentTimeMillis();
        mySort(arr);
        t2 = System.currentTimeMillis();
        System.out.println(" "+(t2-t1));
        
        
        System.out.println("Время сортировки при диапазоне значений 100 000:");
        int[] b = new int[length];
        for(int i = 0; i<length; i++){
            arr[i] = rand.nextInt(100000);
            b[i] = arr[i];
        }
        t1 =  System.currentTimeMillis();
        mySort(arr);
        t2 = System.currentTimeMillis();
        System.out.println(" "+(t2-t1));
        
        
        System.out.println("сложность О(n+k), где k-диапазон значений");
        
    }
    
    
}
